|
In mathematics, the sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieve of Eratosthenes, which marks off multiples of primes, it does some preliminary work and then marks off multiples of ''squares'' of primes, thus achieving a better theoretical asymptotic complexity. It was created in 2003 by A. O. L. Atkin and Daniel J. Bernstein.〔A.O.L. Atkin, D.J. Bernstein, (''Prime sieves using binary quadratic forms'' ), Math. Comp. 73 (2004), 1023-1030.()〕 == Algorithm == In the algorithm: * All remainders are modulo-sixty remainders (divide the number by 60 and return the remainder). * All numbers, including and , are positive integers. * Flipping an entry in the sieve list means to change the marking (prime or nonprime) to the opposite marking. * This results in numbers with an odd number of solutions to the corresponding equation being potentially prime (prime if they are also square free), and numbers with an even number of solutions being composite. The algorithm: # Create a results list, filled with 2, 3, and 5. # Create a sieve list with an entry for each positive integer; all entries of this list should initially be marked non prime (composite). # For each entry number in the sieve list, with modulo-sixty remainder : ## If is 1, 13, 17, 29, 37, 41, 49, or 53, flip the entry for each possible solution to . The number of flipping operations as a ratio to the sieving range for this step approaches }}〔 × (the "8" in the fraction comes from the eight modulos handled by this quadratic and the 60 because Atkin calculated this based on an even number of modulo 60 wheels), which results in a fraction of about 0.1117010721276.... ## If is 7, 19, 31, or 43, flip the entry for each possible solution to . The number of flipping operations as a ratio to the sieving range for this step approaches 〔 × (the "4" in the fraction comes from the four modulos handled by this quadratic and the 60 because Atkin calculated this based on an even number of modulo 60 wheels), which results in a fraction of about 0.072551974569.... ## If is 11, 23, 47, or 59, flip the entry for each possible solution to . The number of flipping operations as a ratio to the sieving range for this step approaches 〔 × (the "4" in the fraction comes from the four modulos handled by this quadratic and the 60 because Atkin calculated this based on an even number of modulo 60 wheels), which results in a fraction of about 0.060827679704.... ## If is something else, ignore it completely. # Start with the lowest number in the sieve list. # Take the next number in the sieve list still marked prime. # Include the number in the results list. # Square the number and mark all multiples of that square as non prime. Note that the multiples that can be factored by 2, 3, or 5 need not be marked, as these will be ignored in the final enumeration of primes. # Repeat steps four through seven. The total number of operations for these repetitions of marking the squares of primes as a ratio of the sieving range is the sum of the inverse of the primes squared, which approaches the prime zeta function(2) of 0.45224752004... minus , , and for those primes which have been eliminated by the wheel, with the result multiplied by for the ratio of wheel hits per range; this results in a ratio of about 0.01363637571.... Adding the above ratios of operations together, the above algorithm takes a constant ratio of flipping/marking operations to the sieving range of about 0.2587171021...; From an actual implementation of the algorithm, the ratio is about 0.25 for sieving ranges as low as 67. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Sieve of Atkin」の詳細全文を読む スポンサード リンク
|